package Aleehot100;

/**
 * ClassName: c043
 * Package: Aleehot100
 * Description: 树是否是搜索二叉树
 *
 * @Author BCXJ
 * @Create 2025/7/11 14:33
 * @Version 1.0
 * @Since 1.0
 */
public class c043 {
    public static void main(String[] args) {
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode7 = new TreeNode(7);
        treeNode5.left = treeNode4;
        treeNode5.right = treeNode6;
        treeNode6.right = treeNode3;
        treeNode6.left = treeNode7;

        System.out.println(isValidBST(treeNode5));

    }
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static boolean isValidBST(TreeNode node) {
        return process(node, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private static boolean process(TreeNode node, long minValue, long maxValue) {
        if(node == null) {
            return true;
        }

        if(process(node.left, minValue, node.val) && process(node.right, node.val, maxValue)) {
            return ((node.left == null || node.val > node.left.val) && node.val > minValue) && ((node.right == null || node.val < node.right.val) && node.val < maxValue);
        }
        return false;
    }




    /*
        // 中序遍历的实现
    public static boolean isValidBST(TreeNode root) {

        if (root == null) {
            return true;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode pre = null;
        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                if (pre != null && pre.val >= cur.val) {
                    return false;
                }
                pre = cur;
                cur = cur.right;
            }
        }
        return true;
    }
     */

}
